位元枚舉

在程式、演算法的世界中，很多問題往往用二進位去看後，都可以得到實作起來很簡單的做法，而且二進位能表達的事情遠比我們想像的多！舉凡有或沒有、是或不是、開還是不開這類有兩種選擇的問題，都可以用二進位的角度去看待。

而對電腦來說，二進位下有很多實用的工具可以輔助解決問題，其中最為代表性的就是 bitwise operation ，有了它我們往往可以很高效地處理二進位的資訊，配合前面將問題用二進位來表示，它是一個非常強大的工具

在程式和演算法的世界中，善用二進位的概念經常能夠提供簡單而高效的解決方案。二進位不僅僅是電腦基本的組成，它能表達的範疇遠超我們的想像。所有的有或無、是或非、開或關這類有兩種選擇的問題，都可以從二進位的角度去解釋。

而且對電腦來說，二進位提供了許多實用的工具以協助解決問題，其中最具代表性的就是位元運算（bitwise operations）。通過位元運算，我們能夠很有效率地處理二進位的資訊。例如：實現快速的乘法、除法或取模運算。且位元運算對應集合的概念，使得它能高效解決一些集合的交集、聯集等問題。

例題 1

Codeforces 1097B

彼得剛買了一輛新車，當他抵達聖彼得堡最知名的加油站加油時，突然發現汽油箱上有一個組合鎖！這把鎖有一個範圍為 360 度的刻度盤，一開始指針指向零度。

彼得致電他的汽車經銷商，經銷商告訴他必須旋轉鎖轉恰好 n 次。第 i 次旋轉應為 a_i 度，可以是順時針或逆時針旋轉，並且在剛好 n 次旋轉後，指針應再次指向零度。

這讓彼得感到有些困惑，因為他不確定哪些旋轉應該順時針進行、哪些應該逆時針進行。由於旋轉鎖的方式有很多，請幫助他找出是否存在至少一種方式，使得在所有 n 次旋轉後，指針將再次指向零度？

解法

這邊如果要暴力解決的話，很直覺可以想到枚舉我每次應該順時針轉還是逆時針轉？因為每次有兩種可能，共要轉 n 次，因此這樣一來時間複雜度會是 。

不過概念簡單，但要怎麼實作呢？這是不少初學者會卡關的地方，這邊可以將整個選取狀況視作一個「二進位的數」，其中 1 代表順時針轉、0 代表逆時針轉。如此一來就可如下實作：

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    for (int i = 0; i < (1 << n); ++i) {
        int sum = 0;
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                sum += a[j];
            } else {
                sum -= a[j];
            }
        }
        if (sum % 360 == 0) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

因為共有 n 次旋轉，因此令 i 在 之間跑可以被用作枚舉 n 次旋轉的所有組合，而之後只要用右移運算子來取得第 j 個 bit 是 0 還是 1 就可以存取該次的組合了！

這樣的總時間複雜度是 ，在 的測試資料下很輕鬆